{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "40494696",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30 和 24 的最大公约数是 6\n",
      "满足贝祖等式的整数解为：30*1 + 24*-1 = 6\n"
     ]
    }
   ],
   "source": [
    "def extended_euclidean_algorithm(a, b):\n",
    "    x1, y1, x2, y2 = 1, 0, 0, 1\n",
    "    \n",
    "    while b:\n",
    "        q = a // b\n",
    "        a, b = b, a % b\n",
    "        x1, x2 = x2, x1 - q * x2\n",
    "        y1, y2 = y2, y1 - q * y2\n",
    "\n",
    "    return a, x1, y1\n",
    "\n",
    "# 示例\n",
    "num1 = 30\n",
    "num2 = 24\n",
    "gcd_result, x, y = extended_euclidean_algorithm(num1, num2)\n",
    "print(f'{num1} 和 {num2} 的最大公约数是 {gcd_result}')\n",
    "print(f'满足贝祖等式的整数解为：{num1}*{x} + {num2}*{y} = {gcd_result}')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ba7e66dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 和 7 的最大公约数是 1\n",
      "满足贝祖等式的整数解为：3*-2 + 7*1 = 1\n"
     ]
    }
   ],
   "source": [
    "def gcd(a, b):\n",
    "    if a < b :\n",
    "          a, b = b, a\n",
    "    while a % b != 0 :\n",
    "          a, b = b, a % b\n",
    "    return b\n",
    "\n",
    "def ext_gcd(a, b):\n",
    "    if b == 0:\n",
    "        return 1, 0\n",
    "    else:\n",
    "        x, y = ext_gcd(b, a%b)\n",
    "        x, y = y, x - (a//b) * y\n",
    "        return x, y\n",
    "    \n",
    "num1 = 3\n",
    "num2 = 7\n",
    "x, y = ext_gcd(num1, num2)\n",
    "print(f'{num1} 和 {num2} 的最大公约数是 {gcd(num1, num2)}')\n",
    "print(f'满足贝祖等式的整数解为：{num1}*{x} + {num2}*{y} = {gcd(num1, num2)}')\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
